|
|
Výpočetní složitost v teorii grafů
Melka, Jakub ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků.
|
|
|
Immersions and edge-disjoint linkages
Klimošová, Tereza ; Dvořák, Zdeněk (vedoucí práce) ; Kráľ, Daniel (oponent)
Grafové imerze jsou přirozená analogie k intenzivně zkoumanému konceptu grafových minorů a topologických grafových minorů, ale teorie v této oblasti je mnohem méně rozvinutá. V práci se zabýváme hledáním postačujících podmínek pro existenci imerzí a vlastnostmi grafů, které neobsahují imerzi daného grafu. Dokazujeme, že velká stromová šířka hranově čtyřsouvislého grafu implikuje existenci imerze libovolného čtyřregulárního grafu na malém počtu vrcholů, a že velký maximální stupeň hranově třisouvislého grafu implikuje existenci imerze libovolného třiregulárního grafu na malém počtu vrcholů.
|
|
|
Optimalizace na grafech s omezenou stromovou šířkou přes vlastnosti vyjádřitelné v MSOL
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Kráľ, Daniel (oponent)
Courcellova věta mluví o výpočetní složitosti rozhodovacích problémů defino- vaných formulemi monadické logiky druhého řádu nad relačními strukturami s omezenou stromovou šířkou. Pro pevnou stromovou šířku a vstupní formuli dává Courcellova věta algoritmus, který formuli rozhodne v lineárním čase nad strukturou dané stro- mové šířky. Práce podává samostatný důkaz Courcellovy věty pomocí metod teorie konečných modelů. Dále obsahuje důkazy všech potřebných prerekvizit hlavního důkazu, zejména v teorii konečných modelů široce využívané Ehrenfeuchtovy-Fraïssého věty. Práce též obsahuje implementaci algoritmu plynoucího z tohoto důkazu. Nakonec nastiňuje aktuální stav výzkumu dané oblasti a z něj plynoucí možnosti. 1
|
|
|
Délkově omezené řezy v grafech
Berg, Michal ; Kolman, Petr (vedoucí práce) ; Dvořák, Pavel (oponent)
V této práci se budeme zabývat problémem délkově omezeného řezu, nazývaného také L-omezený řez. Ukážeme kombinatorický algoritmus pro hledání minimálního L-omezeného řezu na grafech omezené stromové šířky založený na dynamickém programování. Následně také ukážeme, že se tento algoritmus dá použít i pro hledání L-omezeného řezu na rovinných grafech. Také se podíváme na problém (dG(s, t) + 1)-omezeného řezu. Je známé, že tento problém je NP-těžký na obecných grafech. Ale to, jestli je NP-těžký i na rovinných grafech se speciálními vrcholy na vnější stěně, je otevřený problém. Pokusíme se nastínit způsob, kterým bychom možná mohli ukázat, že tento problém je řešitelný v polynomiálním čase.
|
|
|
Treewidth, Extended Formulations of CSP and MSO Polytopes, and their Algorithmic Applications
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Fellows, Michael R. (oponent) ; Tantau, Till (oponent)
Tato práce podává důkaz existence kompaktních rozšířených formulací pro širokou škálu polytopů souvisejících s problémem omezujících podmínek (CSP), grafovou monadickou logikou druhého řádu (MSO) a rozšířeními MSO, mají-li dané instance omezenou stromovou šířku. Ukážeme, že naše rozšířené formulace mají další užitečné vlastnosti a odkrýváme souvislosti mezi MSO a CSP. Docházíme tak k závěru, že kombinace MSO logiky, CSP a geometrie poskytuje rozšiřitelný rámec pro konstrukci kompaktních rozšířených formulací a parametrizovaných algoritmů pro grafy s omezenou stromovou šířkou. S použitím těchto nástrojů pak zcela zodpovíme otázku parametrizované složitosti různých rozšíření MSO na dvou třídách grafů, konkrétně grafech s omezenou stromovou šířkou a s omezenou různorodostí sousedství. Objevili jsme, že (ne)linearita těchto rozšíření určuje parametrizovanou složitost na grafech s omezenou různorodostí sousedství. Na závěr studujeme tzv. posunutou kombinatorickou optimalizaci, která tvoří nelineární optimalizační rámec zobecňující standardní kombinatorickou optimalizaci. V této oblasti poskytneme prvotní zjištění z perspektivy parametrizované složitosti.
|
|
|
Parity vertex colorings
Soukup, Jan ; Gregor, Petr (vedoucí práce) ; Kučera, Petr (oponent)
Paritní cesta ve vrcholovém barvení grafu G je cesta ve které je každá barva použita sudě-krát. Paritní vrcholové barvení je barvení, které nemá žádnou paritní cestu. Nechť χp(G) je minimální počet barev v paritním bar- vení grafu G. Je známo, že χp(Bn) ≥ √ n, kde Bn je úplný binární strom s n vrstvami. Dokážeme, že platí ostrá nerovnost, a pomocí tohoto odhadu dokážeme nový odhad χp(T) > 3 √ log n, kde T je libovolný binární strom s n vrcholy. Dále se zabýváme časovou složitostí výpočtu paritního chromatického čísla χp(G). Dokážeme, že ověřování korektnosti paritního vrcholového bar- vení je coNP-úplné a popíšeme exponenciální algoritmus, který ho počítá. Dále pomocí Courcelleho věty dokážeme že existuje FPT algoritmus parame- trizovaný počtem barev k a stromovou šířkou grafu G ověřující že χp(G) ≤ k. Navíc popíšeme náš vlastní FPT algoritmus řešící tento problém. Tento al- goritmus běží v polynomiálním čase pro omezené k a stromovou šířku G. Na- konec zkoumáme příbuznost tohoto barvení s dalšími barveními, konkrétně s unique maximum, conflict free a parity edge barveními.
|
|
|
Výpočetní složitost v teorii grafů
Melka, Jakub ; Kratochvíl, Jan (vedoucí práce) ; Fiala, Jiří (oponent)
V předložené práci studujeme problém rekonstrukce grafu ze seznamu uzavřených okolí vrcholů tohoto grafu. Tento problém, původně zformulovaný V. Sósovou, budeme zkoumat z hlediska teorie parametrizované složitosti a zobecníme jej na problém rekonstruovatelnosti vzhledem ke třídám grafů. V této práci dokážeme, že tento problém leží ve třídě složitosti FPT vzhledem k parametru omezené stromové šířky a omezeného maximálního stupně nebo ke 2-degenerovaných grafům s omezeným počtem jistých indukovaných podgrafů, kde parametr je počet těchto podgrafů. Dále dokážeme, že problém rekonstruovatelnosti vzhledem ke třídě grafů s omezeným vrcholovým pokrytím leží ve třídě složitosti XP. Na závěr dokážeme vzájemnou nezávislost získaných výsledků.
|
|
|
Immersions and edge-disjoint linkages
Klimošová, Tereza ; Dvořák, Zdeněk (vedoucí práce) ; Kráľ, Daniel (oponent)
Grafové imerze jsou přirozená analogie k intenzivně zkoumanému konceptu grafových minorů a topologických grafových minorů, ale teorie v této oblasti je mnohem méně rozvinutá. V práci se zabýváme hledáním postačujících podmínek pro existenci imerzí a vlastnostmi grafů, které neobsahují imerzi daného grafu. Dokazujeme, že velká stromová šířka hranově čtyřsouvislého grafu implikuje existenci imerze libovolného čtyřregulárního grafu na malém počtu vrcholů, a že velký maximální stupeň hranově třisouvislého grafu implikuje existenci imerze libovolného třiregulárního grafu na malém počtu vrcholů.
|
|
|
Optimalizace na grafech s omezenou stromovou šířkou přes vlastnosti vyjádřitelné v MSOL
Koutecký, Martin ; Kolman, Petr (vedoucí práce) ; Kráľ, Daniel (oponent)
Courcellova věta mluví o výpočetní složitosti rozhodovacích problémů defino- vaných formulemi monadické logiky druhého řádu nad relačními strukturami s omezenou stromovou šířkou. Pro pevnou stromovou šířku a vstupní formuli dává Courcellova věta algoritmus, který formuli rozhodne v lineárním čase nad strukturou dané stro- mové šířky. Práce podává samostatný důkaz Courcellovy věty pomocí metod teorie konečných modelů. Dále obsahuje důkazy všech potřebných prerekvizit hlavního důkazu, zejména v teorii konečných modelů široce využívané Ehrenfeuchtovy-Fraïssého věty. Práce též obsahuje implementaci algoritmu plynoucího z tohoto důkazu. Nakonec nastiňuje aktuální stav výzkumu dané oblasti a z něj plynoucí možnosti. 1
|
host ::
RSS.